还没有笔记
选中页面文字后点击「高亮」按钮添加
1.1. 带余数的长除法。循环群的故事与初等数论（因式分解、素数、同余）密切相关。我们使用关于 $\mathbb{N}$ 中加法、乘法和序的一些结果，从“第一原理”证明一些基本事实。其中一个最基本的事实如下：
定理 1.1.1（带余数的长除法）。设 $n \in \mathbb{N}$。则对于所有 $a \in \mathbb{Z}$，存在唯一的整数 $q$ 和 $r$，其中 $0 \leq r \leq n-1$，使得 $a=n q+r$。
这里 $q$ 代表商，$r$ 代表余数。
证明。存在性：定义 $\mathbb{Z}$ 的子集 $X$ 为
首先，我们断言 $X \neq \emptyset$。如果 $a \geq 0$，取 $q=0$，则 $a-n q=a \geq 0$ 是 $X$ 的一个元素。如果 $a<0$，取 $q=a=-k$（例如），其中 $k>0$。则 $a-n q=-k+n k=k(n-1) \geq 0$，因为 $k>0$ 且 $n-1 \geq 0$。因此 $a-n a \in X$，所以 $X \neq \emptyset$。
接下来，我们断言 $X$ 有一个最小元素。如果 $0 \in X$，则 $0$ 显然是 $X$ 的最小元素。如果 $0 \notin X$，则 $X \subseteq \mathbb{N}$，因此，由于 $X \neq \emptyset$，根据良序原理，$X$ 有一个最小元素。在任何情况下，令 $r$ 是 $X$ 的最小元素。则根据定义，$r=a-n q$ 且 $r \geq 0$。注意 $a=n q+r$。为了证明定理的存在性部分，只需证明 $r \leq n-1$。我们通过反证法论证：如果 $r \geq n$，则 $0 \leq r-n<r$。但是
由于 $r-n \geq 0$，根据 $X$ 的定义，$r-n \in X$。但 $r-n<r$，这与选择 $r$ 作为 $X$ 的最小元素相矛盾。因此 $r \leq n-1$ 且 $a=n q+r$。
唯一性：假设 $a=n q_{1}+r_{1}=n q_{2}+r_{2}$，其中 $q_{i}, r_{i} \in \mathbb{Z}$ 且 $0 \leq r_{i} \leq n-1$，对于 $i=1,2$。我们必须证明 $q_{1}=q_{2}$ 且 $r_{1}=r_{2}$。现在 $r_{1} \leq r_{2}$ 或 $r_{2} \leq r_{1}$。通过对称性，我们可以假设 $r_{1} \leq r_{2}$。则
此外，
如果 $r_{2}-r_{1} \neq 0$，则 $r_{2}-r_{1}$ 是一个可被 $n$ 整除的正整数，因此 $r_{2}-r_{1} \geq n$。这与 $r_{2}-r_{1} \leq n-1$ 相矛盾。因此 $r_{2}-r_{1}=0$，即 $r_{2}=r_{1}$。则 $n\left(q_{1}-q_{2}\right)=0$。由于 $n \in \mathbb{N}$，$n \neq 0$。因此 $q_{1}-q_{2}=0$，所以 $q_{1}=q_{2}$。
推论 1.1.2。设 $n \in \mathbb{N}$。同余类 $[a]_{n} \in \mathbb{Z} / n \mathbb{Z}$ 的每个等价类都有一个唯一的代表 $r$，其中 $0 \leq r \leq n-1$。因此 $\#(\mathbb{Z} / n \mathbb{Z})=n$，并且作为一个集合，
证明。给定 $[a]_{n} \in \mathbb{Z} / n \mathbb{Z}$，写 $a=n q+r$，其中 $0 \leq r \leq n-1$。则 $a \equiv r \bmod n$，所以 $[a]_{n}=[r]_{n}$。为了证明 $r$ 是 $[a]_{n}$ 的唯一代表，使得 $0 \leq r \leq n-1$，假设 $\left[r_{1}\right]_{n}=\left[r_{2}\right]_{n}$ 且 $0 \leq r_{1}, r_{2} \leq n-1$。则 $a=n q_{1}+r_{1}=n q_{2}+r_{2}$ 对于某些整数 $q_{1}, q_{2}$，因此根据定理 1.1.1 的唯一性陈述，$r_{1}=r_{2}$。
推论 1.1.3。设 $G$ 是一个群，设 $g \in G$ 是一个（有限）阶为 $n$ 的元素。则，对于所有 $N \in \mathbb{Z}$，$g^{N}=1 \Longleftrightarrow n \mid N$。
证明。设 $N \in \mathbb{Z}$ 是任意的。则 $N=n q+r$，其中 $0 \leq r \leq n-1$，并且 $n \mid N \Longleftrightarrow r=0$，且
此外，根据阶的定义，$0 \leq r \leq n-1$，则 $g^{r} \neq 1$。因此，对于 $0 \leq r \leq n-1$，$g^{r}=1 \Longleftrightarrow r=0$。因此 $g^{N}=1 \Longleftrightarrow n \mid N$。
我们已经看到推论 1.1.3 意味着，如果 $g \in G$ 的阶为 $n$，则 $\langle g\rangle \cong \mathbb{Z} / n \mathbb{Z}$。实际上，存在一个唯一的同构 $f: \mathbb{Z} / n \mathbb{Z} \rightarrow\langle g\rangle$ 使得 $f\left([1]_{n}\right)=g$。此外，$\langle g\rangle$ 的每个元素都可以唯一地写成 $g^{r}, 0 \leq r \leq n-1$。因此 $\#(\langle g\rangle)=n$。
推论 1.1.4。每个循环群都同构于 $\mathbb{Z}$ 或 $\mathbb{Z} / n \mathbb{Z}$。
证明。每个循环群 $G$ 都形如 $\langle g\rangle$，对于某个 $g \in G$。证明然后遵循命题 3.2.4，如果 $g$ 有无限阶，以及上述 (iii) 如果 $g$ 有有限阶。
从现在开始，我们将专注于群 $\mathbb{Z}$ 和 $\mathbb{Z} / n \mathbb{Z}$。前一个推论告诉我们，任何针对 $\mathbb{Z}$ 或 $\mathbb{Z} / n \mathbb{Z}$ 证明的代数结果（例如，关于子群的性质或元素的阶）都将对任意循环群有自然的类似物。
命题 1.1.5。$\mathbb{Z}$ 的每个子群都是循环群。
证明。设 $H \leq \mathbb{Z}$。如果 $H=\{0\}$，则 $H=\langle 0\rangle$，因此 $H$ 是循环群。因此我们可以假设存在一个 $a \in H, a \neq 0$。则 $-a \in H$ 也是，并且 $a>0$ 或 $-a>0$。特别地，集合 $H \cap \mathbb{N}$ 是非空的。令 $d$ 是 $H \cap \mathbb{N}$ 的最小元素，根据良序原理，该元素存在。为了证明该命题，我们将证明 $H=\langle d\rangle$。我们将通过证明 $\langle d\rangle \subseteq H$ 和 $H \subseteq\langle d\rangle$ 来实现。
由于 $d \in H \cap \mathbb{N}$，$d \in H$，因此 $\langle d\rangle \subseteq H$。所以我们必须证明 $H \subseteq\langle d\rangle$。设 $a \in H$；我们必须证明 $a \in\langle d\rangle$。对 $a$ 应用带余数的长除法，我们可以写成 $a=d q+r$，其中 $0 \leq r \leq d-1$。正如我们所见，$\langle d\rangle \subseteq H$，因此 $d q=q \cdot d \in H$。由于 $H$ 是一个子群，$-d q \in H$，并且，由于 $a \in H, a-d q=r \in H$。如果 $r>0$，则 $r \in \mathbb{N}, r \in H$，且 $r \leq d-1<d$。这与选择 $d$ 作为 $H$ 的最小正元素相矛盾。因此 $r=0$，即 $a-d q=0$，因此 $a=d q \in\langle d\rangle$。由此可见 $H \subseteq\langle d\rangle$，因此 $H=\langle d\rangle$。因此 $H$ 是循环群。
备注 1.1.6。证明还表明，如果 $H \leq \mathbb{Z}$ 不是平凡子群 $\{0\}$，则 $H=\langle d\rangle \subseteq$ 本身是一个无限循环群。因此 $H \cong \mathbb{Z}$，并且 $H$ 的两个生成元是 $\pm d$。
一个非常类似的论证表明：
命题 1.1.7。设 $n \in \mathbb{N}$。则 $\mathbb{Z} / n \mathbb{Z}$ 的每个子群 $H$ 都是循环群。
证明。在这种情况下，我们设
则 $X$ 是一个有限集。如前所述，存在一个最小元素 $d \in X$，因此 $[d]_{n} \in H$。我们断言 $H=\left\langle[d]_{n}\right\rangle$。显然 $\left\langle[d]_{n}\right\rangle \subseteq H$。反之，如果 $[k]_{n} \in H$，我们可以写成 $k=d q+s$，其中 $0 \leq s \leq d-1$。则 $[k]_{n}=[d q+s]_{n}=q \cdot[d]_{n}+[s]_{n}$。由此可见 $[s]_{n}=q \cdot[d]_{n}-[k]_{n} \in H$。由于 $0 \leq s \leq d-1<d \leq n-1$，根据 $d$ 的定义，我们必须有 $s=0$。因此 $[k]_{n} \in\left\langle[d]_{n}\right\rangle$。由此可见 $H \subseteq\left\langle[d]_{n}\right\rangle$，因此 $H=\left\langle[d]_{n}\right\rangle$。
这里，我们使用循环群同构于 $\mathbb{Z}$ 或 $\mathbb{Z} / n \mathbb{Z}$ 的结果，以及前面在练习 2.31 中讨论的事实：如果 $f: G_{1} \rightarrow G_{2}$ 是一个同构，则 $G_{1}$ 的子集 $H$ 是 $G_{1}$ 的子群 $\Longleftrightarrow f(H)$ 是 $G_{2}$ 的子群，并且（使用练习 2.19），如果 $H=\langle g\rangle$ 是 $G_{1}$ 的循环子群，则 $f(\langle g\rangle)$ 是 $G_{2}$ 的循环子群，实际上它是 $\langle f(g)\rangle$。因此函数 $H \mapsto f(H)$ 是从 $G_{1}$ 的子群集合到 $G_{2}$ 的子群集合的双射，并且在这种情况下 $H$ 和 $f(H)$ 是同构的。特别地，$H$ 是循环群 $\Longleftrightarrow f(H)$ 是循环群。
$\mathbb{Z}$ 的每个子群都可以唯一地描述为 $\langle 0\rangle$ 或 $\langle d\rangle$，其中 $d>0$。我们将在后面给出 $\mathbb{Z} / n \mathbb{Z}$ 的子群及其可能的生成元的类似精确描述。
1.2. 因式分解。回想一下，如果 $a, b \in \mathbb{Z}$，则 $a \mid b \Longleftrightarrow$ 存在一个 $k \in \mathbb{Z}$ 使得 $b=a k \Longleftrightarrow b$ 是 $a$ 的倍数 $\Longleftrightarrow b \in\langle a\rangle \Longleftrightarrow\langle b\rangle \subseteq\langle a\rangle$。我们有以下关于可除性的简单性质：
(1) 对于所有 $a \in \mathbb{Z}$，$a \mid a$。
(2) 可除性是传递的：如果 $a \mid b$ 且 $b \mid c$，则 $a \mid c$。
(3) 如果 $a \mid b$ 且 $a \mid c$，则，对于所有 $r, s \in \mathbb{Z}$，$a \mid(r b+s c)$。
(4) 对于所有 $a \in \mathbb{Z}$，$a \mid 0$，但 $0 \mid a \Longleftrightarrow a=0$。
(5) 对于所有 $a \in \mathbb{Z}$，$1 \mid a$，但 $a \mid 1 \Longleftrightarrow a= \pm 1$。
(6) 对于所有 $a, b \in \mathbb{Z}$，如果 $a \mid b$ 且 $b \mid a$，则 $b= \pm a$。
定义 1.2.1。设 $a, b \in \mathbb{Z}$，不都为 $0$。$a$ 和 $b$ 的最大公约数（记作 $\operatorname{gcd}(a, b)$）是一个 $d \in \mathbb{N}$ 使得 $d|a, d| b$，并且，对于所有 $e \in \mathbb{Z}$，如果 $e \mid a$ 且 $e \mid b$，则 $e \mid d$。（有时人们将 gcd 写作 $(a, b)$，但这会与有序对混淆。）
引理 1.2.2。如果 $a$ 和 $b$ 的 gcd 存在，则它是唯一的。
证明。如果 $d_{1}$ 和 $d_{2}$ 是 $a$ 和 $b$ 的两个 gcd，则 $d_{1} \mid d_{2}$ 且 $d_{2} \mid d_{1}$。根据上述 (6)，由于根据定义 $d_{1}, d_{2} \in \mathbb{N}$，$d_{1}=d_{2}$。
备注 1.2.3。(i) 如果 $d$ 是 $a$ 和 $b$ 的 gcd，则根据定义，它是一个自然数，同时整除 $a$ 和 $b$ 的最大值。然而，$d$ 具有定义中更强的性质。
(ii) 从小学起，计算 $\operatorname{gcd}(a, b)=d$ 的一个熟悉方法是将 $a$ 和 $b$ 分解成素数幂的乘积。然后 $d$ 的素因子是同时整除 $a$ 和 $b$ 的素数，并且素数 $p$ 在 $d$ 的因式分解中出现的幂如下：如果 $p^{n_{1}}$ 是整除 $a$ 的 $p$ 的最大幂，并且 $p^{n_{2}}$ 是整除 $b$ 的 $p$ 的最大幂，则整除 $d$ 的 $p$ 的最大幂是 $p^{\min \left(n_{1}, n_{2}\right)}$。然而，有更计算有效的方法来寻找 $\operatorname{gcd}(a, b)$，这些方法不涉及将 $a$ 和 $b$ 因式分解成素数（这是一个计算上非常困难的问题）。
以下结果告诉我们 gcd 总是存在的：
定理 1.2.4。设 $a, b \in \mathbb{Z}$，不都为 $0$。
(i) $a$ 和 $b$ 的 gcd 存在，并且根据前面备注中的 (i)，它必然是唯一的。
(ii) 如果 $d$ 是 $a$ 和 $b$ 的 gcd，则存在 $n, m \in \mathbb{Z}$ 使得 $d=\operatorname{gcd}(a, b)=a n+b m$。
(iii) 对于所有 $c \in \mathbb{Z}$，存在 $x, y \in \mathbb{Z}$ 使得 $a x+b y=c \Longleftrightarrow d \mid c$。
证明。(i) 考虑集合
根据定义，如果 $c \in \mathbb{Z}$，则 $c \in H \Longleftrightarrow$ 存在 $x, y \in \mathbb{Z}$ 使得 $a x+b y=c$。我们断言 $H$ 是 $\mathbb{Z}$ 的一个包含 $a$ 和 $b$ 的子群；实际上，它是前面定义的由 $a$ 和 $b$ 生成的子群 $\langle a, b\rangle$（因为 $a x+b y=x \cdot a+y \cdot b$）。我们将直接证明这一点：首先，$H$ 在加法下是封闭的，因为给定 $H$ 的两个元素 $a x_{1}+b y_{1}, a x_{2}+b y_{2}$，
显然，$0=a \cdot 0+b \cdot 0 \in H$，并且如果 $a x+b y \in H$，则 $-(a x+b y)=a(-x)+b(-y) \in H$。因此 $H$ 是一个子群。此外，注意 $a=a \cdot 1+b \cdot 0 \in H$ 且 $b=a \cdot 0+b \cdot 1 \in H$。
由于 $\mathbb{Z}$ 的每个子群都是循环群，存在一个 $d \in \mathbb{Z}$ 使得 $H=\langle d\rangle$。此外，$H \neq\{0\}$ 因为 $a, b \in H$ 并且根据假设至少其中一个非零。因此我们可以假设 $d>0$，即 $d \in \mathbb{N}$。为了完成 (i) 的证明，只需证明 $d$ 是 $a$ 和 $b$ 的 gcd。由于 $a \in H=\langle d\rangle, d \mid a$。类似地，$d \mid b$。因此，$d$ 是 $a$ 和 $b$ 的一个公约数。最后，如果 $e \mid a$ 且 $e \mid b$，则 $e \mid a n+b m=d$。因此 $d=\operatorname{gcd}(a, b)$。
(ii) 通过构造，对于如 (i) 中的 $d=\operatorname{gcd}(a, b)$，我们看到 $d \in H$，因此 $d=a n+b m$ 对于某些 $n, m \in \mathbb{Z}$。
(iii) 所有形如 $a x+b y$ 的整数 $c$ 的集合根据定义是 (i) 证明中的子群 $H$。那里的论证表明 $H=\langle d\rangle$ 是 $d$ 的所有倍数的集合。将这两个事实结合起来，$c=a x+b y$ 对于某些 $x, y \in \mathbb{Z} \Longleftrightarrow c \in\langle d\rangle \Longleftrightarrow d \mid c$。
在单独一节中，我们将描述一个高效计算过程，即欧几里得算法，用于寻找两个整数 $a, b$（不都为 $0$）的 gcd $d$，以及如何将 $d$ 写成 $a$ 和 $b$ 的线性组合 $a n+b m$。
备注 1.2.5。在 (i) 的证明中使用的论证表明：如果 $G$ 是一个阿贝尔群，并且群运算用 $+$ 表示，且 $g_{1}, \ldots, g_{k} \in G$，则集合
是 $G$ 的一个包含 $g_{1}, \ldots, g_{k}$ 的子群（实际上它是最小的此类子群）。
定义 1.2.6。设 $a, b \in \mathbb{Z}$，不都为 $0$。如果 $\operatorname{gcd}(a, b)=1$，则 $a$ 和 $b$ 互为素数。换句话说，如果一个整数 $e$ 同时整除 $a$ 和 $b$，则 $e$ 整除 $1$，或等价地 $e= \pm 1$。
引理 1.2.7。给定不都为 $0$ 的整数 $a$ 和 $b$，$a$ 和 $b$ 互为素数 $\Longleftrightarrow$ 存在 $x, y \in \mathbb{Z}$ 使得 $a x+b y=1$。
证明。根据前一个推论，存在 $x, y \in \mathbb{Z}$ 使得 $a x+b y=1 \Longleftrightarrow d=\operatorname{gcd}(a, b)$ 整除 $1 \Longleftrightarrow d=1$。
然后我们有以下基本结果：
命题 1.2.8。设 $a, b \in \mathbb{Z}$ 互为素数。如果 $a \mid b c$，则 $a \mid c$。
证明。根据前一个推论，存在 $x, y \in \mathbb{Z}$ 使得 $a x+b y=1$。则 $c= c(a x)+c(b y)=a(c x)+(b c) y$。根据假设，$a \mid b c$ 并且显然 $a \mid a$。因此 $a \mid(a(c x)+(b c) y)=c$。
该推论最常应用于素数：
定义 1.2.9。设 $p \in \mathbb{N}$。则 $p$ 是素数或素数，如果 $p>1$，并且对于所有 $n \in \mathbb{N}$，如果 $n \mid p$，则 $n=1$ 或 $n=p$。
然后我们有素数的以下性质：
引理 1.2.10。设 $p$ 是一个素数，设 $n \in \mathbb{Z}$。则 $p$ 和 $n$ 互为素数，或者 $p \mid n$。
证明。设 $d=\operatorname{gcd}(p, n)$。则 $d \in \mathbb{N}$ 且 $d \mid p$。因此，$d=1$ 或 $d=p$。如果 $d=1$，则根据定义 $p$ 和 $n$ 互为素数。如果 $d=p$，则 $p \mid n$。
推论 1.2.11。设 $p$ 是一个素数，设 $a, b \in \mathbb{Z}$。如果 $p \mid a b$，则 $p \mid a$ 或 $p \mid b$。换句话说，如果一个素数整除一个乘积，则它整除其中一个因子。
证明。假设 $p$ 不整除 $a$。则根据引理 1.2.10，$p$ 和 $a$ 互为素数。则根据命题 1.2.8，$p$ 整除 $b$。
推论 1.2.12。设 $p$ 是一个素数，设 $a_{1}, \ldots, a_{k} \in \mathbb{Z}$。如果 $p \mid a_{1} \cdots a_{k}$，则存在一个 $i$ 使得 $p \mid a_{i}$。
证明。这由上述内容和直接的归纳论证得出。
前一个推论是以下内容的关键步骤之一：
定理 1.2.13（算术基本定理）。设 $n \in \mathbb{N}, n>1$。则 $n$ 可以唯一地因式分解成素数。更精确地说，存在素数 $p_{1}, \ldots, p_{r}$ 使得 $n=p_{1} \cdots p_{r}$，并且这种乘积的唯一性在于，如果
其中 $p_{i}$ 和 $q_{j}$ 是素数，则 $r=s$，并且，在可能重新排序之后，$q_{i}=p_{i}$ 对于每个 $i$。
证明。存在性：我们已经通过对 $n$ 的完全归纳法证明了这一点。
唯一性：假设 $p_{1} \cdots p_{r}=q_{1} \cdots q_{s}$，其中 $p_{i}$ 和 $q_{j}$ 是素数。我们通过对 $r$ 的归纳法论证。如果 $r=1$，则 $p_{1}=q_{1} \cdots q_{s}$，其中 $q_{j}$ 是素数。因此 $s=1$，否则 $p_{1}$ 将有一个非平凡因式分解，然后 $p_{1}=q_{1}$。对于归纳步骤，假设我们已经证明了 $r-1$ 的定理。设 $p_{1} \cdots p_{r}=q_{1} \cdots q_{s}$。则左侧是 $p_{r}$ 的倍数，因此 $p_{r}$ 整除 $q_{1} \cdots q_{s}$。因此，存在一个 $i$ 使得 $p_{r} \mid q_{i}$。由于 $q_{i}$ 是一个素数，$p_{r}=q_{i}$。在重新标记 $q_{i}$ 之后，我们可以假设 $i=s$。则
因此在抵消最后一个因子后，我们有 $p_{1} \cdots p_{r-1}=q_{1} \cdots q_{s-1}$。根据归纳假设，$s-1=r-1$，即 $s=r$，因此 $q_{r}=p_{r}$，并且，在重新标记之后，我们可以假设 $q_{i}=p_{i}$，$1 \leq i \leq r-1$。这完成了归纳步骤，因此完成了定理的证明。
备注 1.2.14。通常我们将自然数 $n>1$ 唯一地写成 $n=p_{1}^{n_{1}} \cdots p_{r}^{n_{r}}$，其中 $p_{i}$ 是素数且 $p_{1}<\cdots<p_{r}$，而 $n_{i}$ 是正整数。
1.3. 欧几里得算法。正如承诺的那样，我们描述一种计算有效的方法来寻找两个正整数 $a$ 和 $b$ 的 gcd，同时展示如何将 gcd 写成 $a$ 和 $b$ 的线性组合。
从 $a, b$ 开始。写成 $a=b q_{1}+r_{1}$，其中整数 $q_{1}$ 和 $r_{1}, 0 \leq r_{1}<b$。注意 $r_{1}=a+b\left(-q_{1}\right)$ 是 $a$ 和 $b$ 的线性组合。如果 $r_{1}=0$，停止，否则用 $b$ 和 $r_{1}$ 代替 $a$ 和 $b$ 重复此过程，使得 $b=r_{1} q_{2}+r_{2}$，其中 $0 \leq r_{2}<r_{1}$，并注意 $r_{2}=b-r_{1} q_{2}=b-a q_{2}+b q_{1} q_{2}$ 仍然是 $a$ 和 $b$ 的线性组合。如果 $r_{2}=0$，停止，否则用 $r_{1}$ 和 $r_{2}$ 代替 $b$ 和 $r_{1}$ 再次重复，使得 $r_{1}=r_{2} q_{3}+r_{3}$，其中 $0 \leq r_{3}<r_{2}$。我们可以这样继续下去，找到 $r_{1}>r_{2}>r_{3}>\cdots>r_{k} \geq 0$，其中 $r_{k-1}=r_{k} q_{k+1}+r_{k+1}$。由于 $r_{i}$ 序列是递减的，并且它们都是非负整数，最终这个过程必须停止，得到一个 $r_{n}$ 使得 $r_{n+1}=0$，因此 $r_{n-1}=r_{n} q_{n+1}$。过程如下所示：
我们断言 $r_{n}$ 是 $a$ 和 $b$ 的 gcd。实际上，我们将证明：
(i) $r_{n}$ 同时整除 $a$ 和 $b$；
(ii) $r_{n}$ 是 $a$ 和 $b$ 的线性组合。
(i) 由于 $r_{n} \mid r_{n-1}$，方程 $r_{n-2}=r_{n-1} q_{n}+r_{n}$ 意味着 $r_{n} \mid r_{n-2}$，然后从方程 $r_{k-1}=r_{k} q_{k+1}+r_{k+1}$ 倒推（使用逆向归纳法），我们看到 $r_{n} \mid r_{k-1}$ 对于所有 $k<n$。$b=r_{1} q_{2}+r_{2}$ 并且 $r_{n}$ 整除 $r_{1}$ 和 $r_{2}$ 的事实意味着 $r_{n}$ 整除 $b$，然后方程 $a=b q_{1}+r_{1}$ 意味着 $r_{n}$ 也整除 $a$。
(ii) 反过来，我们已经看到 $r_{1}$ 和 $r_{2}$ 是 $a$ 和 $b$ 的线性组合。通过归纳法，如果 $r_{k-1}$ 和 $r_{k}$ 是 $a$ 和 $b$ 的线性组合，则方程 $r_{k-1}=r_{k} q_{k+1}+r_{k+1}$ 意味着 $r_{k+1}=r_{k-1}-r_{k} q_{k+1}$ 也是 $a$ 和 $b$ 的线性组合（因为正如我们在课堂上所看到的，$a$ 和 $b$ 的所有线性组合的集合是 $\mathbb{Z}$ 的一个子群，因此在加法、减法和整数乘法下是封闭的）。因此 $r_{n}$ 也是 $a$ 和 $b$ 的线性组合。但我们已经看到，如果 $a$ 和 $b$ 的线性组合整除 $a$ 和 $b$ 并且是正的，则它等于 $a$ 和 $b$ 的 gcd。所以 $r_{n}$ 是 $a$ 和 $b$ 的 gcd。
该算法比解释起来更容易执行！例如，要找到 $34$ 和 $38$ 的 gcd，我们有
这表示 $2=\operatorname{gcd}(34,38)$ 并且 $2=34-4(8)=34-(38-34)(8)=9(34)+(-8)(38)$。
选择 $q_{k+1}$ 和 $r_{k+1}$ 使得 $r_{k-1}=r_{k} q_{k+1} \pm r_{k+1}$，其中 $r_{k+1}<r_{k}$ 并且符号的选择使得 $r_{k+1}$ 尽可能小，通常更有效。换句话说，我们允许形如 $-r_{k}$ 的负余数，目标是使余数的绝对值最小。例如，要找到 $7$ 和 $34$ 的 gcd，我们可以写成
从而看到 gcd 是 $1$，并且 $1=7-6=7-(34-4(7))=-34+5(7)$，或者我们可以直接看到
一个更复杂的例子如下，找到 $1367$ 和 $298$ 的 gcd：
因此 gcd 是 $1$，稍微有点耐心就可以看出
1.4. $\mathbb{Z} / n \mathbb{Z}$ 的子群。从现在开始，我们将经常省略 $\mathbb{Z} / n \mathbb{Z}$ 元素的括号 $[\cdot]_{n}$，除非我们想比较整数 $a$ 与其在 $\mathbb{Z} / n \mathbb{Z}$ 中的等价类 $[a]_{n}$，或者我们想将 $a$ 视为在可能不同的 $n$ 下 $\mathbb{Z} / n \mathbb{Z}$ 的一个元素，在这种情况下我们将为了强调而写成 $[a]_{n}$。请注意，$\mathbb{Z} / n \mathbb{Z}$ 有两种代数运算：加法和乘法。此外，对于整数 $a, b$，
例如，$a \cdot[b]_{n}$ 是加法群 $\mathbb{Z} / n \mathbb{Z}$ 中的“指数”记法：如果 $a>0$，则 $a \cdot[b]_{n}=\underbrace{[b]_{n}+\cdots+[b]_{n}}_{a \text { 次 }}$。
我们首先给出方程 $a x=b$ 在 $\mathbb{Z} / n \mathbb{Z}$ 中有解的判据，或等价地，同余方程 $a x \equiv b \bmod n$ 在整数中有解的判据。首先，有以下观察：
引理 1.4.1。设 $n \in \mathbb{N}$，设 $d \in \mathbb{N}$ 是 $n$ 的一个因子。
(i) 如果 $a \in \mathbb{Z}$，则 $d \mid a \Longleftrightarrow[a]_{n} \in\left\langle[d]_{n}\right\rangle$。
(ii) 如果 $a, a^{\prime}$ 是整数使得 $a \equiv a^{\prime} \bmod n$，则 $d|a \Longleftrightarrow d| a^{\prime}$。
(iii) 如果 $a, a^{\prime} \in \mathbb{Z}$ 且 $a \equiv a^{\prime} \bmod n$，则 $\operatorname{gcd}(a, n)=\operatorname{gcd}\left(a^{\prime}, n\right)$。
证明。(i) $\Longrightarrow$：如果 $a=k d$，则 $[a]_{n}=[k d]_{n}=k \cdot[d]_{n}$，因此 $[a]_{n} \in\left\langle[d]_{n}\right\rangle$。$\Longleftarrow$：如果 $[a]_{n} \in\left\langle[d]_{n}\right\rangle$，则 $[a]_{n}=k \cdot[d]_{n}=[k d]_{n}$ 对于某个整数 $k$，因此 $a=k d+\ell n$ 对于整数 $k, \ell$。由于 $d \mid k d$ 且 $d|n, d| a$。
(ii) 根据 (i)，$d \mid a \Longleftrightarrow[a]_{n} \in\left\langle[d]_{n}\right\rangle \Longleftrightarrow\left[a^{\prime}\right]_{n} \in\left\langle[d]_{n}\right\rangle$（因为 $\left.\left[a^{\prime}\right]_{n}=[a]_{n}\right) \Longleftrightarrow d \mid a^{\prime}$。
(iii) 根据 (ii)，$e \in \mathbb{N}$ 同时整除 $a$ 和 $n \Longleftrightarrow e$ 同时整除 $a^{\prime}$ 和 $n$。因此，$a$ 和 $n$ 的公约数集合与 $a^{\prime}$ 和 $n$ 的公约数集合相同。因此，$a$ 和 $n$ 的最大公约数与 $a^{\prime}$ 和 $n$ 的最大公约数相同。
推论 1.4.2。函数 $f\left([a]_{n}\right)=\operatorname{gcd}(a, n)$ 是从 $\mathbb{Z} / n \mathbb{Z}$ 到 $\{1, \ldots, n\}$ 的一个良定义函数。特别地，如果 $a, a^{\prime} \in \mathbb{Z}$ 且 $a \equiv a^{\prime} \bmod n$，则 $a$ 和 $n$ 互为素数 $\Longleftrightarrow a^{\prime}$ 和 $n$ 互为素数，因此陈述 $[a]_{n}$ 和 $n$ 互为素数是良定义的。
我们现在回到将 $\mathbb{Z} / n \mathbb{Z}$ 的元素写成整数的惯例，但有时会模糊整数与 $\mathbb{Z} / n \mathbb{Z}$ 元素之间的区别。
命题 1.4.3。给定 $a, c \in \mathbb{Z} / n \mathbb{Z}$，存在一个 $x \in \mathbb{Z} / n \mathbb{Z}$ 使得 $ax =c \Longleftrightarrow c \in\langle d\rangle$，其中 $d=\operatorname{gcd}(a, n)$。
证明。为了避免 $\mathbb{Z}$ 的元素与 $\mathbb{Z} / n \mathbb{Z}$ 的元素之间的混淆，我们把方程重写为 $[a]_{n}[x]_{n}=[c]_{n}$ 并确定它何时有整数解 $x$。方程 $[a]_{n}[x]_{n}=[c]_{n}$ 有整数解 $x \Longleftrightarrow$ 存在一个整数 $x$ 使得 $a x \equiv c \bmod n$。但是 $a x \equiv c \bmod n$ 有整数解 $x \Longleftrightarrow c$ 和 $a x$ 相差 $n$ 的倍数，即存在一个整数 $y$ 使得 $c=a x+n y$。我们已经看到这个条件等价于：$d \mid c$。根据引理 1.4.1(i)，这个条件等价于：$[c]_{n} \in\left\langle[d]_{n}\right\rangle$。去掉 $[\cdot]_{n}$ 记号，这等价于 $c \in\langle d\rangle$。
推论 1.4.4。给定 $a \in \mathbb{Z} / n \mathbb{Z}$，存在一个 $x \in \mathbb{Z} / n \mathbb{Z}$ 使得 $ax =1$，即 $a$ 是 $(\mathbb{Z} / n \mathbb{Z}, \cdot)$ 的一个可逆元素 $\Longleftrightarrow \operatorname{gcd}(a, n)=1$，即 $a$ 和 $n$ 互为素数。
回想一下 $(\mathbb{Z} / n \mathbb{Z})^{*}$ 是二元结构 $(\mathbb{Z} / n \mathbb{Z}, \cdot)$ 中的可逆元素集合。特别地，$\left((\mathbb{Z} / n \mathbb{Z})^{*}, \cdot\right)$ 是一个阿贝尔群。上述推论的陈述是：
每当我们写 $(\mathbb{Z} / n \mathbb{Z})^{*}$ 时，群运算被理解为乘法。请注意，$(\mathbb{Z} / n \mathbb{Z})^{*}$ 不是 $\mathbb{Z} / n \mathbb{Z}$ 的子群（其中运算必然是 $+$）。
示例 1.4.5。(i) $(\mathbb{Z} / 6 \mathbb{Z})^{*}=\{1,5\}$。必然有 $(\mathbb{Z} / 6 \mathbb{Z})^{*} \cong \mathbb{Z} / 2 \mathbb{Z}$ 并且 $5$ 的阶为 $2$，即在 $\mathbb{Z} / 6 \mathbb{Z}$ 中 $5^{2}=1$。
(ii) $(\mathbb{Z} / 5 \mathbb{Z})^{*}=\{1,2,3,4\}$，因此 $\#\left((\mathbb{Z} / 5 \mathbb{Z})^{*}\right)=4$。很容易看出 $(\mathbb{Z} / 5 \mathbb{Z})^{*}$ 是循环群。实际上，$2^{2}=4,2^{3}=3$，并且 $2^{4}=1$，因此 $(\mathbb{Z} / 5 \mathbb{Z})^{*}=\langle 2\rangle$。
(iii) 另一方面，$ (\mathbb{Z} / 8 \mathbb{Z})^{*}=\{1,3,5,7\}$，因此 $\#((\mathbb{Z} / 8 \mathbb{Z}))^{*}=4$。但是 $(\mathbb{Z} / 8 \mathbb{Z})^{*}$ 不是循环群，因为 $3^{2}=5^{2}=7^{2}=1$。因此 $(\mathbb{Z} / 8 \mathbb{Z})^{*}$ 的每个元素的阶为 $1$ 或 $2$。特别地，$(\mathbb{Z} / 8 \mathbb{Z})^{*}$ 中没有阶为 $4$ 的元素，因此 $(\mathbb{Z} / 8 \mathbb{Z})^{*}$ 不是循环群。
定义 1.4.6。通过以下方式定义欧拉 $\phi$ 函数 $\phi: \mathbb{N} \rightarrow \mathbb{N}$：
因此 $\phi(n)$ 是整数 $a$ 的数量，其中 $0 \leq a \leq n-1$，使得 $\operatorname{gcd}(a, n)=1$。
命题 1.4.7。如果 $p$ 是素数，$\phi(p)=p-1$。更一般地，如果 $p$ 是素数且 $k \in \mathbb{N}$，则
证明。假设 $p^{k}$ 是一个素数幂，其中 $p$ 是素数且 $k \in \mathbb{N}$，包括 $k=1$ 的情况。则整数 $a$ 与 $p^{k}$ 不互为素数 $\Longleftrightarrow$ 它与 $p$ 有一个公因子 $\Longleftrightarrow p \mid k \Longleftrightarrow k$ 是 $p$ 的倍数。现在在 $0$ 到 $p^{k}-1$ 之间有 $p^{k} / p=p^{k-1}$ 个 $p$ 的倍数。因此，与 $p^{k}$ 互为素数的整数 $a$ 的数量，其中 $0 \leq a \leq p^{k}-1$，是 $\phi\left(p^{k}\right)=p^{k}-p^{k-1}=p^{k-1}(p-1)$。
一般来说，对于 $n>1, 1 \leq \phi(n) \leq n-1$，并且很容易看出 $\phi(n)=n-1 \Longleftrightarrow n$ 是素数。$\phi$ 的前几个值的表格如下：
| $n$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| $\phi(n)$ | 1 | 1 | 2 | 2 | 4 | 2 | 6 | 4 | 6 | 4 | 10 | 4 |
我们很快将描述函数 $\phi(n)$ 的更多性质。
我们回到描述 $\mathbb{Z} / n \mathbb{Z}$ 所有子群的问题。以下定理给出了完整的描述。
定理 1.4.8。设 $n \in \mathbb{N}$。
(i) $\mathbb{Z} / n \mathbb{Z}$ 的每个子群都是循环群。
(ii) 如果 $a \in \mathbb{Z} / n \mathbb{Z}$ 且 $d=\operatorname{gcd}(a, n)$，则 $\langle a\rangle=\langle d\rangle$。
(iii) 如果 $a \in \mathbb{Z} / n \mathbb{Z}$ 且 $d=\operatorname{gcd}(a, n)$，$a$ 的阶是 $n / d=n / \operatorname{gcd}(a, n)$。
(iv) $\mathbb{Z} / n \mathbb{Z}$ 的每个子群的阶整除 $n$。
(v) 对于 $n$ 的每个因子 $d$，$\mathbb{Z} / n \mathbb{Z}$ 中恰好有一个阶为 $d$ 的子群，即 $\langle n / d\rangle$。
证明。(i) 我们已经看到这一点。
(ii) 由于 $d \mid a, a \in\langle d\rangle$，因此 $\langle a\rangle \subseteq\langle d\rangle$。反之，根据命题 1.4.3，由于 $d \mid d$，存在一个 $x$ 使得 $a x=d$，因此 $x \cdot a=d$，因此 $d \in\langle a\rangle$。因此 $\langle d\rangle \subseteq\langle a\rangle$。由此可见 $\langle a\rangle=\langle d\rangle$。
(iii) 根据 (ii)，$\langle a\rangle=\langle d\rangle$，因此 $a$ 的阶，我们知道是 $\#(\langle a\rangle)$，等于 $\#(\langle d\rangle)$，因此等于 $d$ 的阶。显然 $(n / d) \cdot d=n=0$ 在 $\mathbb{Z} / n \mathbb{Z}$ 中，因此 $d$ 的阶至多是 $n / d$。另一方面，如果 $0<k<n / d$，则，将 $d$ 视为整数，$0<k \cdot d<n$，因此 $k \cdot d \neq 0$ 在 $\mathbb{Z} / n \mathbb{Z}$ 中。因此 $n / d$ 是最小的正整数 $k$ 使得 $k \cdot d=0$。所以 $d$ 的阶以及 $a$ 的阶是 $n / d$。
(iv) 如果 $H \leq \mathbb{Z} / n \mathbb{Z}$，则 $H=\langle a\rangle$ 对于某个 $a$，并且 $H$ 的阶就是 $a$ 的阶，即 $n / d$ 对于 $n$ 的某个因子 $d$。但显然 $n / d$ 整除 $n$。
(v) 根据 (i) 和 (ii)，$\mathbb{Z} / n \mathbb{Z}$ 的每个子群 $H$ 形如 $\langle e\rangle$，对于 $n$ 的某个因子 $e$。根据 (iii)，$H$ 的阶是 $n / e$。因此 $\mathbb{Z} / n \mathbb{Z}$ 中阶为 $d$ 的唯一子群是 $\langle e\rangle$，其中 $n / e=d$，即 $e=n / d$。
推论 1.4.9。$\langle a\rangle=\mathbb{Z} / n \mathbb{Z}$，即 $a$ 是 $\mathbb{Z} / n \mathbb{Z}$ 的生成元 $\Longleftrightarrow \operatorname{gcd}(a, n)=1 \Longleftrightarrow a \in(\mathbb{Z} / n \mathbb{Z})^{*}$。
证明。$\langle a\rangle=\mathbb{Z} / n \mathbb{Z} \Longleftrightarrow a$ 的阶是 $n \Longleftrightarrow$ 对于 $d=\operatorname{gcd}(a, n), n / d=n \Longleftrightarrow d=1$。
给定 $a \in(\mathbb{Z} / n \mathbb{Z})^{*}$，请注意不要混淆 $a$ 作为 $\mathbb{Z} / n \mathbb{Z}$ 的元素的阶与 $a$ 作为 $(\mathbb{Z} / n \mathbb{Z})^{*}$ 的元素的阶。作为 $\mathbb{Z} / n \mathbb{Z}$ 的元素，$a$ 总是具有阶 $n$ 根据上述推论。但作为 $(\mathbb{Z} / n \mathbb{Z})^{*}$ 的元素，$a$ 的阶可能是 $1$（如果 $a=1$），并且通常至多是 $\phi(n)$。
所有上述内容都可以转换到更一般的有限循环群的背景下。
推论 1.4.10。设 $G$ 是一个阶为 $n$ 的有限循环群，设 $g$ 是 $G$ 的一个生成元。则：
(i) $G$ 的每个子群都是循环群，并且 $G$ 的每个子群的阶整除 $n$。
(ii) 如果 $a \in \mathbb{Z}$ 且 $d=\operatorname{gcd}(a, n)$，则 $\left\langle g^{a}\right\rangle=\left\langle g^{d}\right\rangle$。此外，$g^{a}$ 的阶是 $n / d$。特别地，$g^{a}$ 是 $G$ 的一个生成元 $\Longleftrightarrow \operatorname{gcd}(a, n)=1$。
(iii) 对于 $n$ 的每个因子 $d$， $G$ 中恰好有一个阶为 $d$ 的子群，即 $\left\langle g^{n / d}\right\rangle$。
(iv) $G$ 的生成元的数量是 $\phi(n)$。
证明。只需对 $G=\mathbb{Z} / n \mathbb{Z}$ 进行验证，它遵循我们之前的结果。
示例 1.4.11。群 $\mu_{n}$ 是循环群；实际上，$\mu_{n}=\left\langle e^{2 \pi i / n}\right\rangle$。一个 $n$ 次单位根 $z$ 是一个原 $n$ 次单位根，如果 $z^{n}=1$ 但没有更小的 $z$ 的幂等于 $1$，即 $z$ 在群 $\mu_{n}$ 中的阶是 $n$。这只是说 $z$ 是 $\mu_{n}$ 的一个生成元，因此根据 (ii) 等价于 $z=e^{2 a \pi i / n}$ 且 $\operatorname{gcd}(a, n)=1$ 的陈述。
示例 1.4.12。考虑群 $(\mathbb{Z} / 7 \mathbb{Z})^{*}$，阶为 $6$。请注意 $2^{2}=4$ 和 $2^{3}=1$。因此 $2$ 的阶是 $3$，而不是 $(\mathbb{Z} / 7 \mathbb{Z})^{*}$ 的生成元。但是 $3^{2}=2,3^{3}=6=-1$，因此 $3^{6}=(-1)^{2}=1$。根据一般结果，这表明 $3$ 的阶必须整除 $6$。正如我们所看到的，阶不是 $2$ 或 $3$，因此 $3$ 的阶是 $6$ 并且 $(\mathbb{Z} / 7 \mathbb{Z})^{*}=\langle 3\rangle$ 恰好是循环群。
上述推论表明 $(\mathbb{Z} / 7 \mathbb{Z})^{*}$ 恰好有一个阶为 $1,2,3,6$ 的子群，并且这些是所有子群。实际上，它告诉我们如何找到它们：阶为 $1$ 的子群是 $\left\langle 3^{6}\right\rangle=\langle 1\rangle$，阶为 $2$ 的子群是 $\left\langle 3^{3}\right\rangle=\langle 6\rangle=\langle-1\rangle$，阶为 $3$ 的子群是 $\left\langle 3^{2}\right\rangle=\langle 2\rangle$，以及阶为 $6$ 的子群是 $\langle 3\rangle$。此外，$(\mathbb{Z} / 7 \mathbb{Z})^{*}$ 的生成元恰好是 $3^{a}$，其中 $a$ 是模 $6$ 取值且 $\operatorname{gcd}(a, 6)=1$。$a$ 的唯一可能性是 $1$ 和 $5$，因此 $(\mathbb{Z} / 7 \mathbb{Z})^{*}$ 的生成元是 $3^{1}=3$ 和 $3^{5}=3^{-1}=5$。
推论 1.4.13。对于每个 $d \mid n$，$\mathbb{Z} / n \mathbb{Z}$ 中恰好有 $\phi(d)$ 个阶为 $d$ 的元素。
证明。给定 $a \in \mathbb{Z} / n \mathbb{Z}$，$a$ 的阶是 $d \Longleftrightarrow \#(\langle a\rangle)=d \Longleftrightarrow\langle a\rangle=\langle n / d\rangle \Longleftrightarrow a \in\langle n / d\rangle$ 并且 $a$ 是 $\langle n / d\rangle$ 的生成元。由于 $\langle n / d\rangle$ 是一个阶为 $d$ 的循环群，根据前一个推论，它恰好有 $\phi(d)$ 个生成元。因此 $\mathbb{Z} / n \mathbb{Z}$ 中恰好有 $\phi(d)$ 个阶为 $d$ 的元素 $a$。
备注 1.4.14。实际上，给定 $d \mid n$，$\mathbb{Z} / n \mathbb{Z}$ 中阶为 $d$ 的 $\phi(d)$ 个元素的集合被标识为集合
推论 1.4.13 导致以下欧拉 $\phi$ 函数的递归恒等式：
推论 1.4.15。对于每个自然数 $n$，
证明。根据定理的 (iii)，$\mathbb{Z} / n \mathbb{Z}$ 的每个元素的阶都整除 $n$。根据推论 1.4.13，对于每个 $d \mid n$，$\mathbb{Z} / n \mathbb{Z}$ 中恰好有 $\phi(d)$ 个阶为 $d$ 的元素。因此和 $\sum_{d \mid n} \phi(d)$ 统计了 $\mathbb{Z} / n \mathbb{Z}$ 中元素的数量，即 $n$。
例如，$20$ 的因子是 $1,2,4,5,10$ 和 $20$。我们有
备注 1.4.16。如果 $G$ 是一个有限循环群，则 $G$ 的每个子群的阶都整除 $G$ 的阶。实际上，正如我们将看到的，这对于每个有限群都成立，被称为拉格朗日定理：如果 $G$ 是一个有限群且 $H \leq G$，则 $\#(H) \mid \#(G)$。然而，$\mathbb{Z} / n \mathbb{Z}$ 对于 $n=\#(\mathbb{Z} / n \mathbb{Z})$ 的每个因子 $d$ 恰好有一个阶为 $d$ 的子群，这是 $\mathbb{Z} / n \mathbb{Z}$（或更一般的有限循环群）的一个非常特殊的性质。对于一般的有限群 $G$ 和 $\#(G)$ 的一个因子 $d$，可能不存在阶为 $d$ 的子群，或者存在多个（如 $(\mathbb{Z} / 2 \mathbb{Z}) \times (\mathbb{Z} / 2 \mathbb{Z}), D_{3}$ 或 $Q$ 的情况）。
定理 1.5.1（中国剩余定理）。设 $n, m \in \mathbb{N}$ 且 $\operatorname{gcd}(n, m)=1$。则
等价地，$ (\mathbb{Z} / n \mathbb{Z}) \times (\mathbb{Z} / m \mathbb{Z})$ 是循环群。
一个等价的表述如下：
定理 1.5.2（中国剩余定理版本 2）。设 $n, m \in \mathbb{N}$ 且 $\operatorname{gcd}(n, m)=1$。则，对于所有 $r, s \in \mathbb{Z}$，存在一个 $x \in \mathbb{Z}$ 使得
此外，如果 $x$ 和 $x^{\prime}$ 满足上述同余，则 $x \equiv x^{\prime} \bmod n m$。
以这种形式，该结果在公元 300-500 年间（在中国以及后来的印度和西方）是已知的。
为了证明中国剩余定理，我们首先从以下关于群的一般引理开始，这作为一个练习留下（练习 3.7）：
引理 1.5.3。设 $G_{1}$ 和 $G_{2}$ 是群，设 $g_{1} \in G_{1}$ 且 $g_{2} \in G_{2}$。假设 $g_{1}$ 的有限阶为 $d_{1}$ 且 $g_{2}$ 的有限阶为 $d_{2}$。则群 $G_{1} \times G_{2}$ 中 $\left(g_{1}, g_{2}\right)$ 的阶是 $d_{1}$ 和 $d_{2}$ 的最小公倍数。
中国剩余定理的证明。将引理应用于元素 $(1,1) \in (\mathbb{Z} / n \mathbb{Z}) \times(\mathbb{Z} / m \mathbb{Z})$，我们看到 $(1,1)$ 的阶是 $n$ 和 $m$ 的最小公倍数。一个通用公式（练习 3.6）表明 $n$ 和 $m$ 的最小公倍数等于 $n m / \operatorname{gcd}(n, m)$，因此如果 $\operatorname{gcd}(n, m)=1$，则为 $n m$。（实际上，在 $\operatorname{gcd}(n, m)=1$ 的情况下，很容易直接验证这一点。）因此，在 $\operatorname{gcd}(n, m)=1$ 的假设下，$ (\mathbb{Z} / n \mathbb{Z}) \times(\mathbb{Z} / m \mathbb{Z})$ 有一个阶为 $n m$ 的元素，这正是 $ (\mathbb{Z} / n \mathbb{Z}) \times(\mathbb{Z} / m \mathbb{Z})$ 的阶。因此 $ (\mathbb{Z} / n \mathbb{Z}) \times(\mathbb{Z} / m \mathbb{Z})$ 是循环群，实际上它是由 $(1,1)$ 生成的。
备注 1.5.4。上述证明方法计算了 $ (\mathbb{Z} / n \mathbb{Z}) \times (\mathbb{Z} / m \mathbb{Z})$ 的每个元素的阶，无论 $n$ 和 $m$ 是否互为素数。如果 $\operatorname{gcd}(n, m)>1$，则类似于上述证明的论证表明 $ (\mathbb{Z} / n \mathbb{Z}) \times (\mathbb{Z} / m \mathbb{Z})$ 的每个元素的阶都整除 $n$ 和 $m$ 的最小公倍数，即 $n m / \operatorname{gcd}(n, m)$，因此严格小于 $n m$。因此 $ (\mathbb{Z} / n \mathbb{Z}) \times (\mathbb{Z} / m \mathbb{Z})$ 没有阶为 $n m$ 的元素，因此 $ (\mathbb{Z} / n \mathbb{Z}) \times (\mathbb{Z} / m \mathbb{Z})$ 不是循环群。例如，我们已经看到 $ (\mathbb{Z} / 2 \mathbb{Z}) \times (\mathbb{Z} / 2 \mathbb{Z})$ 中的每个元素的阶为 $1$ 或 $2$。
要看我们上面证明的中国剩余定理版本与版本 2 之间的联系，仍然在 $\operatorname{gcd}(n, m)=1$ 的假设下，回想一下由于元素 $(1,1) \in (\mathbb{Z} / n \mathbb{Z}) \times(\mathbb{Z} / m \mathbb{Z})$ 的阶为 $n m$，存在一个显式同构 $f: \mathbb{Z} / n m \mathbb{Z} \rightarrow(\mathbb{Z} / n \mathbb{Z}) \times(\mathbb{Z} / m \mathbb{Z})$ 由 $f(a)=(a, a)$ 给出。更精确地说，为了跟踪我们正在处理的群，我们可以写成
（回想练习 1.19 中由 $g_{1}\left([a]_{n m}\right)=[a]_{n}$ 定义的函数 $g_{1}: \mathbb{Z} / n m \mathbb{Z} \rightarrow \mathbb{Z} / n \mathbb{Z}$ 是良定义的，因为 $n \mid n m$，同样由 $g_{2}\left([a]_{n m}\right)= [a]_{m}$ 定义的函数 $g_{2}: \mathbb{Z} / n m \mathbb{Z} \rightarrow \mathbb{Z} / m \mathbb{Z}$ 也是良定义的。）由于 $f$ 是一个同构，它也是一个双射。因此，对于每个 $[r]_{n} \in \mathbb{Z} / n \mathbb{Z}$ 和 $[s]_{m} \in \mathbb{Z} / m \mathbb{Z}$，存在一个唯一的 $[x]_{n m} \in \mathbb{Z} / n m \mathbb{Z}$ 使得 $f\left([x]_{n m}\right)=\left([r]_{n},[s]_{m}\right)$。这本质上是中国剩余定理的版本 2。
备注 1.5.5。(1) 还有一个中国剩余定理版本 2 的证明，它给出了 $x$ 的显式方法。
(2) 如果 $n$ 和 $m$ 不一定互为素数，很容易给出同余的充要条件
有一个解。
我们现在转向中国剩余定理的乘法形式。
命题 1.5.6。假设 $\operatorname{gcd}(n, m)=1$，并令 $g$ 表示同构 $f: \mathbb{Z} / n m \mathbb{Z} \rightarrow(\mathbb{Z} / n \mathbb{Z}) \times(\mathbb{Z} / m \mathbb{Z})$ 到 $(\mathbb{Z} / n m \mathbb{Z})^{*}$ 的限制，即 $g=f \mid(\mathbb{Z} / n m \mathbb{Z})^{*}$。
(i) $g$ 的像是 $(\mathbb{Z} / n \mathbb{Z})^{*} \times(\mathbb{Z} / m \mathbb{Z})^{*}$。
(ii) 如果我们用 $f^{*}$ 表示由此产生的双射 $(\mathbb{Z} / n m \mathbb{Z})^{*} \rightarrow(\mathbb{Z} / n \mathbb{Z})^{*} \times(\mathbb{Z} / m \mathbb{Z})^{*}$，则 $f^{*}$ 是一个同构。因此特别地
证明。(i) 这源于这样一个事实：给定 $a \in \mathbb{Z}$，
这是练习 3.5。因此，如果 $[a]_{n m} \in(\mathbb{Z} / n m \mathbb{Z})^{*}, g\left([a]_{n m}\right)=f\left([a]_{n m}\right)=\left([a]_{n},[a]_{m}\right) \in(\mathbb{Z} / n \mathbb{Z})^{*} \times (\mathbb{Z} / m \mathbb{Z})^{*}$。因此 $g$ 的像包含在 $(\mathbb{Z} / n \mathbb{Z})^{*} \times (\mathbb{Z} / m \mathbb{Z})^{*}$ 中，并且 $g$ 是单射，因为 $f$ 是单射。为了证明 $g$ 的像恰好是 $(\mathbb{Z} / n \mathbb{Z})^{*} \times (\mathbb{Z} / m \mathbb{Z})^{*}$，设 $\left([r]_{n},[s]_{m}\right) \in(\mathbb{Z} / n \mathbb{Z})^{*} \times (\mathbb{Z} / m \mathbb{Z})^{*}$。则，由于 $f$ 是满射，存在一个 $[a]_{n m} \in \mathbb{Z} / n m \mathbb{Z}$ 使得 $f\left([a]_{n m}\right)=\left([a]_{n},[a]_{m}\right)= \left([r]_{n},[s]_{m}\right)$。则 $\operatorname{gcd}(a, n)=\operatorname{gcd}(r, n)=1$，类似地 $\operatorname{gcd}(a, m)=\operatorname{gcd}(s, m)=1$。根据练习 3.5，由此可见 $a \in(\mathbb{Z} / n m \mathbb{Z})^{*}$。因此 $g$ 的像是 $(\mathbb{Z} / n \mathbb{Z})^{*} \times (\mathbb{Z} / m \mathbb{Z})^{*}$，并且 $g$ 定义了一个双射
为了证明 $f^{*}$ 是一个同构，我们计算：
因此 $f^{*}\left([a]_{n m}[b]_{n m}\right)=f^{*}\left([a]_{n m}\right) f^{*}\left([b]_{n m}\right)$，所以 $f^{*}$ 是一个同构。
我们得到以下推论：
推论 1.5.7。如果 $\operatorname{gcd}(n, m)=1$，则 $\phi(n m)=\phi(n) \phi(m)$。
这导致显式的 $\phi(n)$ 公式：
推论 1.5.8。假设 $n=p_{1}^{a_{1}} \cdots p_{r}^{a_{r}}$ 是 $n$ 的素因式分解，因此 $p_{1}, \ldots, p_{r}$ 是不同的素数且 $a_{i} \geq 1$。则
（有时这写成 $\varphi(n)=n \prod_{p \mid n}\left(1-\frac{1}{p}\right)$，其中乘积是对所有整除 $n$ 的素数取的。）
稍后我们将讨论（但只会在第二部分证明）：
定理 1.5.9（原根的存在性）。如果 $p$ 是一个素数，则 $(\mathbb{Z} / p \mathbb{Z})^{*}$ 是循环群，因此同构于 $\mathbb{Z} /(p-1) \mathbb{Z}$。
这里，循环群 $(\mathbb{Z} / p \mathbb{Z})^{*}$ 的一个生成元被称为原根。找到这样的生成元本质上是一个试错的问题。然而，我们可以使用以下内容：
引理 1.5.10。设 $G$ 是一个阶为 $n$ 的有限群，不一定假设是阿贝尔群。假设 $g \in G$ 是一个元素，使得 $g^{n}=1$，但对于每个 $d \in \mathbb{N}$ 使得 $d \mid n$ 但 $d \neq n, g^{d} \neq 1$。则 $g$ 的阶是 $n$ 且 $G=\langle g\rangle$，因此 $G$ 是循环群且 $g$ 是一个生成元。
证明。由于 $g^{n}=1$，根据推论 1.1.3，$g$ 的阶是 $n$ 的一个因子。但由于对于 $n$ 的每个真因子 $d$，$g^{d} \neq 1$，因此 $g^{k} \neq 1$ 对于所有 $k<n$，因此 $g$ 的阶是 $n$。然后 $G=\langle g\rangle$，因为 $\langle g\rangle \subseteq G$ 并且两个集合都有 $n$ 个元素。
示例 1.5.11。群 $(\mathbb{Z} / 25 \mathbb{Z})^{*}$ 的阶是 $\phi(25)=4 \cdot 5=20$。取 $2$ 的幂，$2^{2}=4, 2^{3}=8, 2^{4}=16, 2^{5}=32=7, 2^{10}=49=24=-1$，因此 $2^{20}=\left(2^{10}\right)^{2}=(-1)^{2}=1$。这表明 $2$ 的阶整除 $20$，但不等于 $1,2,4,5,10$。因此 $2$ 的阶是 $20$ 且 $(\mathbb{Z} / 25 \mathbb{Z})^{*} \cong \mathbb{Z} / 20 \mathbb{Z}$。
原则上，我们因此可以回答关于 $(\mathbb{Z} / 25 \mathbb{Z})^{*}$ 的所有问题。例如，$(\mathbb{Z} / 25 \mathbb{Z})^{*}$ 中阶为 $20$ 的元素，即 $(\mathbb{Z} / 25 \mathbb{Z})^{*}$ 的生成元，恰好是形如 $2^{a}$ 的元素，其中 $\operatorname{gcd}(a, 20)=1$，并且它们有 $\phi(20)=8$ 个。因此，$(\mathbb{Z} / 25 \mathbb{Z})^{*}$ 的生成元集合是
存在一个唯一的阶为 $10$ 的子群，即 $\left\langle 2^{20 / 10}\right\rangle=\left\langle 2^{2}\right\rangle=\langle 4\rangle$。此外，每个阶为 $10$ 的元素都形如 $2^{2 a}=4^{a}$，其中 $\operatorname{gcd}(a, 10)=1$，并且有 $4$ 个：$a=1,3,7,9$。对于阶为 $1,2,4,5$ 的子群和元素也有类似的描述。
使用定理 1.5.9，可以证明：
定理 1.5.12。(i) 如果 $p$ 是一个奇素数，则
因此，由于 $\operatorname{gcd}\left(p-1, p^{k-1}\right)=1,\left(\mathbb{Z} / p^{k} \mathbb{Z}\right)^{*} \cong \mathbb{Z} /(p-1) p^{k-1} \mathbb{Z}$，并且特别地它是循环群。
(ii) 对于素数 $2, (\mathbb{Z} / 2 \mathbb{Z})^{*}=\{1\},(\mathbb{Z} / 4 \mathbb{Z})^{*} \cong \mathbb{Z} / 2 \mathbb{Z}$，如果 $k \geq 3$，则
请注意，素数 $2$ 是特殊的，因为当 $k \geq 3$ 时，$ (\mathbb{Z} / 2^{k} \mathbb{Z})^{*}$ 不是循环群。
推论 1.5.13。群 $(\mathbb{Z} / n \mathbb{Z})^{*}$ 是循环群 $\Longleftrightarrow n$ 满足以下条件之一：
(1) $n=p^{k}$ 是一个素数幂，其中 $p$ 是一个奇素数。
(2) $n=2 p^{k}$，其中 $p$ 是一个奇素数。
(3) $n=2$ 或 $4$。
我们看到 $(\mathbb{Z} / n \mathbb{Z})^{*}$ 很少是循环群。然而，命题 1.5.6 和归纳法意味着，如果 $n$ 的素因式分解是如上所述的 $p_{1}^{a_{1}} \cdots p_{r}^{a_{r}}$，则
因此，根据定理 1.5.12，$ (\mathbb{Z} / n \mathbb{Z})^{*}$ 仍然是循环群的乘积。这里需要特别注意形如 $\left(\mathbb{Z} / 2^{a} \mathbb{Z}\right)^{*}$ 的可能因子；从上述内容可知，$\left(\mathbb{Z} / 2^{a} \mathbb{Z}\right)^{*} \cong(\mathbb{Z} / 2 \mathbb{Z}) \times\left(\mathbb{Z} / 2^{a-2} \mathbb{Z}\right)$，当 $a>2$ 时它不是循环群，但仍然是循环群的乘积。
上述是一个更一般结果的特例：
定理 1.5.14（有限阿贝尔群基本定理）。每个有限阿贝尔群都同构于循环群的乘积。
定理中还有一个唯一性陈述，它有点复杂，但大致意思是阿贝尔群表示为循环群乘积的唯一性失败是由于中国剩余定理，这意味着对于 $\operatorname{gcd}(n, m)=1$，我们可以将一对因子 $(\mathbb{Z} / n \mathbb{Z}) \times (\mathbb{Z} / m \mathbb{Z})$ 替换为 $\mathbb{Z} / n m \mathbb{Z}$。
原则上，有限阿贝尔群基本定理可以告诉我们关于有限阿贝尔群的所有信息，只要我们将其描述为同构于笛卡尔积 $\left(\mathbb{Z} / n_{1} \mathbb{Z}\right) \times \cdots \times\left(\mathbb{Z} / n_{r} \mathbb{Z}\right)$ 并且我们知道正整数 $n_{i}$。例如，原则上可以列出给定阶的所有元素和所有子群。然而，这些计算在实践中可能很困难，并且更像线性代数而不是有限群论。
2.1. 对称群中的计算。回想一下，给定一个集合 $X$，从 $X$ 到自身的所有双射集合 $S_{X}$（或者，更简洁地，特别是当 $X$ 是有限的时候，$X$ 的置换）在函数组合下是一个群。特别地，对于每个 $n \in \mathbb{N}$，对称群 $S_{n}$ 是集合 $\{1, \ldots, n\}$ 的置换群，群运算等于函数组合。因此 $S_{n}$ 是一个有 $n!$ 个元素的群，如果 $n \geq 3$ 则它不是阿贝尔群。如果 $X$ 是一个有 $\#(X)=n$ 个元素的有限集，则对 $X$ 的元素进行标记 $x_{1}, \ldots, x_{n}$ 定义了一个从 $S_{X}$ 到 $S_{n}$ 的同构 $F$。明确地说，给定 $f \in S_{X}$，对于每个 $i, f\left(x_{i}\right)=x_{j}=x_{\sigma(i)}$ 对于某个 $j$ 和唯一的元素 $\sigma \in S_{n}$，我们定义 $F(f)(i)=j$，即 $F(f)=\sigma$。
我们将使用希腊字母 $\sigma, \tau, \rho, \ldots$ 来写 $S_{n}$ 的元素，我们将恒等函数表示为 $1$，我们只使用并置（或偶尔使用乘法符号 $\cdot$）来表示组合（而不是符号 $\circ$）。然而，请记住函数是从右到左工作的：因此 $\sigma \tau(i)= \sigma(\tau(i))$，换句话说，首先计算 $\tau(i)$，然后计算 $\sigma$ 在此结果上的值。
定义 2.1.1。如果 $\sigma(i) \neq i$，我们说 $\sigma$ 移动 $i$，如果 $\sigma(i)=i$，我们说 $\sigma$ 固定 $i$。$\sigma$ 的支撑集 $\operatorname{Supp} \sigma$ 是集合
即由 $\sigma$ 移动的 $\{1, \ldots, n\}$ 的子集。因此 $\operatorname{Supp} \sigma=\emptyset \Longleftrightarrow \sigma=1$。
$S_{n}$ 有许多有趣的子群。例如，由
定义的子集 $H_{n}$ 很容易被验证为 $S_{n}$ 的一个子群，同构于 $S_{n-1}$。实际上，对于所有 $i$，我们可以定义 $H_{i}=\left\{\sigma \in S_{n}: \sigma(i)=i\right\}$。它也同构于 $S_{n-1}$，因为它可以被视为集合 $X=\{1, \ldots, n\}-\{i\}$ 的置换集合，该集合有 $n-1$ 个元素。如果 $n=n_{1}+n_{2}$ 对于两个正整数 $n_{1}, n_{2}$ 则子集
也是 $S_{n}$ 的一个子群。请注意，如果 $\sigma \in H_{n_{1}, n_{2}}$，则自动有
实际上很容易验证 $H_{n_{1}, n_{2}}$ 同构于 $S_{n_{1}} \times S_{n_{2}}$。$S_{n}$ 还有许多其他子群。例如，如果 $\sigma \in S_{n}$ 定义为 $\sigma(i)=i+1$ 对于 $i \leq n-1$，且 $\sigma(n)=1$，则很容易验证 $\sigma$ 的阶是 $n$，因此 $\langle\sigma\rangle$ 是 $S_{n}$ 的一个子群，同构于 $\mathbb{Z} / n \mathbb{Z}$。二面体群 $D_{n}$，即平面中正 $n$ 边形的对称群，通过查看 $n$ 边形顶点的置换，（同构于）$S_{n}$ 的一个子群。请注意，$\#\left(D_{n}\right)=2 n$，因此如果 $n \geq 4$，则 $D_{n}$ 是 $S_{n}$ 的一个真子群。我们将看到（凯莱定理），如果 $G$ 是一个有限群，则存在一个 $n$ 使得 $G$ 同构于 $S_{n}$ 的一个子群（实际上可以取 $n=\#(G)$）。因此，群 $S_{n}$ 相当复杂，因为它们包含所有可能的有限群作为子群，直到同构。
为了描述一个函数 $\sigma:\{1, \ldots, n\} \rightarrow\{1, \ldots, n\}$，不一定是置换，我们可以给出其值的表格，记录 $i$ 然后 $\sigma(i)$，如下所示：
| $i$ | 1 | 2 | $\ldots$ | $n$ |
|---|---|---|---|---|
| $\sigma(i)$ | $\sigma(1)$ | $\sigma(2)$ | $\ldots$ | $\sigma(n)$ |
当然，我们可以通过一个 $2 \times n$ 矩阵来描述相同的信息：
$\sigma$ 是一个置换的条件是整数 $1, \ldots, n$ 在矩阵的第二行中恰好出现一次。当然，第一行是冗余的，$\sigma$ 可以